/*
 * @lc app=leetcode.cn id=654 lang=cpp
 *
 * [654] 最大二叉树
 *
 * https://leetcode-cn.com/problems/maximum-binary-tree/description/
 *
 * algorithms
 * Medium (81.11%)
 * Likes:    413
 * Dislikes: 0
 * Total Accepted:    96.1K
 * Total Submissions: 118.5K
 * Testcase Example:  '[3,2,1,6,0,5]'
 *
 * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
 * 
 * 
 * 创建一个根节点，其值为 nums 中的最大值。
 * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
 * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
 * 
 * 
 * 返回 nums 构建的 最大二叉树 。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：nums = [3,2,1,6,0,5]
 * 输出：[6,3,5,null,2,0,null,null,1]
 * 解释：递归调用如下所示：
 * - [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
 * ⁠   - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
 * ⁠       - 空数组，无子节点。
 * ⁠       - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
 * ⁠           - 空数组，无子节点。
 * ⁠           - 只有一个元素，所以子节点是一个值为 1 的节点。
 * ⁠   - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
 * ⁠       - 只有一个元素，所以子节点是一个值为 0 的节点。
 * ⁠       - 空数组，无子节点。
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：nums = [3,2,1]
 * 输出：[3,null,2,null,1]
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= nums.length <= 1000
 * 0 <= nums[i] <= 1000
 * nums 中的所有整数 互不相同
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
    //     if(nums.size() == 0) return NULL;
    //     int maxVal = INT_MIN;
    //     int maxValIndex = 0;
    //     for(int i = 0; i < nums.size(); i++) {
    //         if(nums[i] > maxVal) {
    //             maxValIndex = i;
    //             maxVal = nums[i];
    //         }
    //     }

    //     TreeNode* root = new TreeNode(maxVal);

    //     vector<int> vecLeft(nums.begin(), nums.begin() + maxValIndex);
    //     vector<int> vecRight(nums.begin() + maxValIndex + 1, nums.end());

    //     root->left = constructMaximumBinaryTree(vecLeft);
    //     root->right = constructMaximumBinaryTree(vecRight);

    //     return root;

    // }
    TreeNode* traversal(vector<int>& nums, int numsBegin, int numsEnd) {

        //第一个点：此种情况下，终止条件判断的是索引，而不是数组，因为数组一直都在用，一直用的是一个数组
        if(numsBegin >= numsEnd) return NULL;


        int maxVal = INT_MIN;
        int maxValIndex;
        //第二个点：循环判断的起始条件是 参数开始的一端，终止条件是 参数结束的一端，
        for(int i = numsBegin; i < numsEnd; i++) {
            if(nums[i] > maxVal) {
                maxVal = nums[i];
                maxValIndex = i;
            } 
        }

        TreeNode* root = new TreeNode(maxVal);
        //加此处的判断是当只有一个元素的时候，就不用进行下边的递归了，
        //该节点就是以子树的根节点出去。
        if(numsEnd - numsBegin == 1) return root;

        //划分数组左边支树的开始端和结束端
        int numsLeftBegin = numsBegin;
        int numsLeftEnd = maxValIndex;

        //划分数组右边支树的开始端和结束端
        int numsRightBegin = maxValIndex + 1;
        int numsRightEnd = numsEnd;


        // 开始递归
        root->left = traversal(nums, numsLeftBegin, numsLeftEnd);
        root->right = traversal(nums, numsRightBegin, numsRightEnd);

        return root;

    }

    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        if(nums.size() == 0) return NULL;
        return traversal(nums, 0, nums.size());
    }
};
// @lc code=end

